#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
SM4Key调度逆向Algorithm

From恢复的前4个轮Key推导主Key
"""

from typing import List

class SM4KeyScheduleReverse:
    """SM4Key调度逆向Class"""
    
    # SM4 S-box
    SM4_SBOX = [
        0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7, 0x16, 0xb6, 0x14, 0xc2, 0x28, 0xfb, 0x2c, 0x05,
        0x2b, 0x67, 0x9a, 0x76, 0x2a, 0xbe, 0x04, 0xc3, 0xaa, 0x44, 0x13, 0x26, 0x49, 0x86, 0x06, 0x99,
        0x9c, 0x42, 0x50, 0xf4, 0x91, 0xef, 0x98, 0x7a, 0x33, 0x54, 0x0b, 0x43, 0xed, 0xcf, 0xac, 0x62,
        0xe4, 0xb3, 0x1c, 0xa9, 0xc9, 0x08, 0xe8, 0x95, 0x80, 0xdf, 0x94, 0xfa, 0x75, 0x8f, 0x3f, 0xa6,
        0x47, 0x07, 0xa7, 0xfc, 0xf3, 0x73, 0x17, 0xba, 0x83, 0x59, 0x3c, 0x19, 0xe6, 0x85, 0x4f, 0xa8,
        0x68, 0x6b, 0x81, 0xb2, 0x71, 0x64, 0xda, 0x8b, 0xf8, 0xeb, 0x0f, 0x4b, 0x70, 0x56, 0x9d, 0x35,
        0x1e, 0x24, 0x0e, 0x5e, 0x63, 0x58, 0xd1, 0xa2, 0x25, 0x22, 0x7c, 0x3b, 0x01, 0x21, 0x78, 0x87,
        0xd4, 0x00, 0x46, 0x57, 0x9f, 0xd3, 0x27, 0x52, 0x4c, 0x36, 0x02, 0xe7, 0xa0, 0xc4, 0xc8, 0x9e,
        0xea, 0xbf, 0x8a, 0xd2, 0x40, 0xc7, 0x38, 0xb5, 0xa3, 0xf7, 0xf2, 0xce, 0xf9, 0x61, 0x15, 0xa1,
        0xe0, 0xae, 0x5d, 0xa4, 0x9b, 0x34, 0x1a, 0x55, 0xad, 0x93, 0x32, 0x30, 0xf5, 0x8c, 0xb1, 0xe3,
        0x1d, 0xf6, 0xe2, 0x2e, 0x82, 0x66, 0xca, 0x60, 0xc0, 0x29, 0x23, 0xab, 0x0d, 0x53, 0x4e, 0x6f,
        0xd5, 0xdb, 0x37, 0x45, 0xde, 0xfd, 0x8e, 0x2f, 0x03, 0xff, 0x6a, 0x72, 0x6d, 0x6c, 0x5b, 0x51,
        0x8d, 0x1b, 0xaf, 0x92, 0xbb, 0xdd, 0xbc, 0x7f, 0x11, 0xd9, 0x5c, 0x41, 0x1f, 0x10, 0x5a, 0xd8,
        0x0a, 0xc1, 0x31, 0x88, 0xa5, 0xcd, 0x7b, 0xbd, 0x2d, 0x74, 0xd0, 0x12, 0xb8, 0xe5, 0xb4, 0xb0,
        0x89, 0x69, 0x97, 0x4a, 0x0c, 0x96, 0x77, 0x7e, 0x65, 0xb9, 0xf1, 0x09, 0xc5, 0x6e, 0xc6, 0x84,
        0x18, 0xf0, 0x7d, 0xec, 0x3a, 0xdc, 0x4d, 0x20, 0x79, 0xee, 0x5f, 0x3e, 0xd7, 0xcb, 0x39, 0x48
    ]
    
    # SM4系统ParametersFK
    FK = [0xa3b1bac6, 0x56aa3350, 0x677d9197, 0xb27022dc]
    
    # 固定ParametersCK
    CK = [
        0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269,
        0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9,
        0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,
        0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9,
        0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229,
        0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
        0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209,
        0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279
    ]
    
    @staticmethod
    def _rotl(x: int, n: int) -> int:
        """32位Loop左移"""
        x = x & 0xFFFFFFFF
        return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF
    
    @staticmethod
    def _tau_transform(x: int) -> int:
        """SM4非线性变换τ (4个并行S-box)"""
        result = 0
        for i in range(4):
            byte_val = (x >> (24 - i * 8)) & 0xFF
            sbox_out = SM4KeyScheduleReverse.SM4_SBOX[byte_val]
            result |= (sbox_out << (24 - i * 8))
        return result
    
    @staticmethod
    def _key_schedule_transform(x: int) -> int:
        """Key调度中的变换FunctionT'"""
        # 应用S-box变换
        tau_result = SM4KeyScheduleReverse._tau_transform(x)
        
        # Key调度的线性变换L'
        # L'(B) = B ⊕ (B ≪ 13) ⊕ (B ≪ 23)
        result = tau_result ^ SM4KeyScheduleReverse._rotl(tau_result, 13) ^ \
                 SM4KeyScheduleReverse._rotl(tau_result, 23)
        
        return result & 0xFFFFFFFF
    @classmethod
    def reverse_from_first_4_round_keys(cls, rk0: int, rk1: int, rk2: int, rk3: int) -> bytes:
        """
        From前4个轮Key逆推主Key
        
        i=0: temp0 = K[1] ⊕ K[2] ⊕ K[3] ⊕ CK[0]
             temp0 = T'(temp0)
             K[0] = K[0] ⊕ temp0
             rk[0] = K[0]  ← 已知
             
        i=1: temp1 = K[2] ⊕ K[3] ⊕ K[0] ⊕ CK[1]
             temp1 = T'(temp1)
             K[1] = K[1] ⊕ temp1
             rk[1] = K[1]  ← 已知
             
        i=2: temp2 = K[3] ⊕ K[0] ⊕ K[1] ⊕ CK[2]
             temp2 = T'(temp2)
             K[2] = K[2] ⊕ temp2
             rk[2] = K[2]  ← 已知
             
        i=3: temp3 = K[0] ⊕ K[1] ⊕ K[2] ⊕ CK[3]
             temp3 = T'(temp3)
             K[3] = K[3] ⊕ temp3
             rk[3] = K[3]  ← 已知
        
        Args:
            rk0, rk1, rk2, rk3: 前4个轮Key（32位Integer）
        
        Returns:
            主KeyMK（16字节）
        """
        # rk[i]就Yes第i轮后的K[i%4]
        # 我们Require逆推To初始的K[0], K[1], K[2], K[3]
        
        # EnsureInputYesPython int而NotYesnumpyClass型
        rk0 = int(rk0)
        rk1 = int(rk1)
        rk2 = int(rk2)
        rk3 = int(rk3)
        
        # Current已知的K值（第4轮后）
        K = [rk0, rk1, rk2, rk3]
        
        # 逆向推导：Fromi=3倒推Toi=0
        for i in range(3, -1, -1):
            temp = K[(i+1)%4] ^ K[(i+2)%4] ^ K[(i+3)%4] ^ cls.CK[i]
            temp = cls._key_schedule_transform(temp)
            
            # K[i%4] = K[i%4] ⊕ temp (正向)
            # 因此：K[i%4]_before = K[i%4]_after ⊕ temp (逆向)
            K[i % 4] = K[i % 4] ^ temp
        
        # 现InK[0], K[1], K[2], K[3]Yes初始值
        # MK[i] = K[i] ⊕ FK[i]
        MK = [K[i] ^ cls.FK[i] for i in range(4)]
        
        # 将MKConvertFor16字节，EnsureUsePython int
        master_key = b''
        for mk_word in MK:
            master_key += int(mk_word).to_bytes(4, 'big')
        
        return master_key
    
    @classmethod
    def verify_master_key(cls, master_key: bytes, rk0: int, rk1: int, rk2: int, rk3: int) -> bool:
        """
        Verify恢复的主KeyYesNo正确
        
        Args:
            master_key: 恢复的主Key（16字节）
            rk0, rk1, rk2, rk3: 已知的前4个轮Key
            
        Returns:
            True if valid, False otherwise
        """
        # From主Key正向Generate轮Key
        MK = [int.from_bytes(master_key[i*4:(i+1)*4], 'big') for i in range(4)]
        K = [MK[i] ^ cls.FK[i] for i in range(4)]
        
        # Generate前4个轮Key
        for i in range(4):
            temp = K[(i+1)%4] ^ K[(i+2)%4] ^ K[(i+3)%4] ^ cls.CK[i]
            temp = cls._key_schedule_transform(temp)
            K[i%4] = K[i%4] ^ temp
            
            # Verify
            if i == 0 and K[0] != rk0:
                return False
            elif i == 1 and K[1] != rk1:
                return False
            elif i == 2 and K[2] != rk2:
                return False
            elif i == 3 and K[3] != rk3:
                return False
        
        return True
